package com.demo.树;

import cn.hutool.core.lang.Console;
import lombok.Getter;
import lombok.Setter;

import java.util.*;

/**
 * @author cl
 */
public class Tree {
    private static Integer tt = Integer.MIN_VALUE;
    public static void main(String[] args) {
        Integer[] tree1 = new Integer[]{1, 2, 3, 4, 5, 6, 7};
        Console.log("递归序为: ");
        print递归序(getTreeByHead(tree1));
        // 先序遍历打印递归序列第一次出现的数值
        System.out.println();
        Console.log("根据递归序推测先序（深度）遍历为(头左右): [1, 2, 4, 5, 3, 6, 7]");
        print先序遍历(getTreeByHead(tree1));
        System.out.println();
        print先序遍历ByStack(getTreeByHead(tree1));
        System.out.println();
        // 中序遍历打印递归序列第二次出现的数值
        Console.log("根据递归序推测中序遍历为(左头右): [4, 2, 5, 1, 6, 3, 7]");
        print中序遍历(getTreeByHead(tree1));
        System.out.println();
        print中序遍历ByStack(getTreeByHead(tree1));
        System.out.println();
        // 后序遍历打印递归序列第三次出现的数值
        Console.log("根据递归序推测后序遍历为(左右头): [4, 5, 2, 6, 7, 3, 1]");
        print后序遍历(getTreeByHead(tree1));
        System.out.println();
        print后序遍历ByStack(getTreeByHead(tree1));
        System.out.println();
        // 宽度优先遍历 按层打印数值
        Console.log("宽度优先遍历: [1, 2, 3, 4, 5, 6, 7]");
        print宽度优先遍历ByQueue(getTreeByHead(tree1));
        System.out.println();
        树的最大宽度1(getTreeByHead(tree1));
        树的最大宽度2(getTreeByHead(tree1));
        Integer[] tree2 = new Integer[]{6, 4, 8, 2, 5, 7, 9, 1, 3};
        Integer max = Integer.MIN_VALUE;
        Console.log("树： {}，是二叉搜索树(BST)1: {}", Arrays.toString(tree1), 判断一个树是二叉搜索树1(getTreeByHead(tree1)));
        tt = Integer.MIN_VALUE;
        Console.log("树： {}，是二叉搜索树(BST)1: {}", Arrays.toString(tree2), 判断一个树是二叉搜索树1(getTreeByHead(tree2)));
        tt = Integer.MIN_VALUE;
        Console.log("树： {}，是二叉搜索树(BST)2: {}", Arrays.toString(tree1), 判断一个树是二叉搜索树2(getTreeByHead(tree1)));
        Console.log("树： {}，是二叉搜索树(BST)2: {}", Arrays.toString(tree2), 判断一个树是二叉搜索树2(getTreeByHead(tree2)));
        Console.log("树： {}，是二叉搜索树(BST)3: {}", Arrays.toString(tree1), 判断一个树是二叉搜索树3(getTreeByHead(tree1)).bst);
        Console.log("树： {}，是二叉搜索树(BST)3: {}", Arrays.toString(tree2), 判断一个树是二叉搜索树3(getTreeByHead(tree2)).bst);
    }

    public static <T> void print递归序(TreeNode<T> treeRoot) {
        if (treeRoot == null) {
            return;
        }
        System.out.printf("%s  ", treeRoot.value);
        print递归序(treeRoot.left);
        System.out.printf("%s  ", treeRoot.value);
        print递归序(treeRoot.right);
        System.out.printf("%s  ", treeRoot.value);
    }

    public static <T> void print先序遍历(TreeNode<T> treeRoot) {
        if (treeRoot == null) {
            return;
        }
        System.out.printf("%s  ", treeRoot.value);
        print先序遍历(treeRoot.left);
        print先序遍历(treeRoot.right);
    }

    /** 通过栈的方式进行先序遍历 */
    /**
     * 1. 头结点入栈
     * 2. 栈顶元素出栈并打印其值，出栈时入栈其右孩子节点和左孩子节点
     * 3. 重复2
     */
    public static <T> void print先序遍历ByStack(TreeNode<T> treeRoot) {
        if (treeRoot != null) {
            Stack<TreeNode<T>> stack = new Stack<>();
            stack.push(treeRoot);
            TreeNode<T> tmp = null;
            while (stack.size() > 0 && (tmp = stack.pop()) != null) {
                System.out.printf("%s  ", tmp.value);
                if (tmp.right != null) {
                    stack.push(tmp.right);
                }
                if (tmp.left != null) {
                    stack.push(tmp.left);
                }
            }
        }
    }

    public static <T> void print中序遍历(TreeNode<T> treeRoot) {
        if (treeRoot == null) {
            return;
        }
        print中序遍历(treeRoot.left);
        System.out.printf("%s  ", treeRoot.value);
        print中序遍历(treeRoot.right);
    }

    /** 通过栈的方式进行中序遍历 */
    /**
     * 1. 全左孩子节点入栈
     * 2. 从栈中取得一个节点打印，并入栈其全左孩子节点
     * 3. 重复1 2
     */
    public static <T> void print中序遍历ByStack(TreeNode<T> treeRoot) {
        if (treeRoot != null) {
            Stack<TreeNode<T>> stack = new Stack<>();
            while (treeRoot != null) {
                stack.push(treeRoot);
                treeRoot = treeRoot.left;
            }
            TreeNode<T> tmp = null;
            while (stack.size() > 0 && (tmp = stack.pop()) != null) {
                System.out.printf("%s  ", tmp.value);
                tmp = tmp.right;
                while (tmp != null) {
                    stack.push(tmp);
                    tmp = tmp.left;
                }
            }
        }
    }

    public static <T> void print后序遍历(TreeNode<T> treeRoot) {
        if (treeRoot == null) {
            return;
        }
        print后序遍历(treeRoot.left);
        print后序遍历(treeRoot.right);
        System.out.printf("%s  ", treeRoot.value);
    }

    /** 通过栈的方式进行后序遍历 */
    /**
     * 1. 头结点入栈
     * 2. 从栈中取得一个节点存储到另一个栈中，并入栈其左孩子节点和右孩子节点
     * 3. 重复1 2
     * 4. 另一个栈出栈打印
     */
    public static <T> void print后序遍历ByStack(TreeNode<T> treeRoot) {
        if (treeRoot != null) {
            Stack<TreeNode<T>> stack = new Stack<>();
            Stack<TreeNode<T>> tmpStack = new Stack<>();
            stack.push(treeRoot);
            TreeNode<T> tmp = null;
            while (stack.size() > 0 && (tmp = stack.pop()) != null) {
                tmpStack.push(tmp);
                if (tmp.left != null) {
                    stack.push(tmp.left);
                }
                if (tmp.right != null) {
                    stack.push(tmp.right);
                }
            }
            while (tmpStack.size() > 0) {
                System.out.printf("%s  ", tmpStack.pop().value);
            }
        }
    }

    /** 通过队列的方式进行宽度优先遍历 */
    /**
     * 1. 头结点入队列
     * 2. 从队列中取得一个节点打印，然后入队列其左孩子节点和右孩子节点
     * 3. 重复 2
     */
    public static <T> void print宽度优先遍历ByQueue(TreeNode<T> treeRoot) {
        if (treeRoot != null) {
            Queue<TreeNode<T>> queue = new LinkedList<>();
            queue.offer(treeRoot);
            TreeNode<T> tmp = null;
            while ((tmp = queue.poll()) != null) {
                System.out.printf("%s  ", tmp.value);
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
            }
        }
    }

    public static <T> void 树的最大宽度1(TreeNode<T> treeRoot) {
        if (treeRoot != null) {
            Map<TreeNode<T>, Integer> map = new HashMap<>();
            Queue<TreeNode<T>> queue = new LinkedList<>();
            Integer currentLevel = 1;
            Integer num = 0;
            Integer max = 0;
            queue.offer(treeRoot);
            map.put(treeRoot, currentLevel);
            TreeNode<T> tmp = null;
            while ((tmp = queue.poll()) != null) {
                if (map.get(tmp).equals(currentLevel)) {
                    // 当前层
                    num++;
                } else {
                    // 下一层
                    currentLevel++;
                    max = max > num ? max : num;
                    num = 1;
                }
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                    map.put(tmp.left, currentLevel + 1);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                    map.put(tmp.right, currentLevel + 1);
                }
            }
            max = max > num ? max : num;
            Console.log("树的最大宽度为: {}, 总层数是: {}", max, currentLevel);
        }
    }

    public static <T> void 树的最大宽度2(TreeNode<T> treeRoot) {
        if (treeRoot != null) {
            Queue<TreeNode<T>> queue = new LinkedList<>();
            Integer currentLevel = 0;
            Integer num = 0;
            Integer max = 0;
            TreeNode<T> currentLevelEnd = null;
            TreeNode<T> levelEnd = treeRoot;
            queue.offer(treeRoot);
            TreeNode<T> tmp = null;
            while ((tmp = queue.poll()) != null) {
                // 当前节点是该层的最后一个节点
                num ++ ;
                if (currentLevelEnd == null) {
                    currentLevelEnd = levelEnd;
                }
                if (tmp == currentLevelEnd) {
                    max = max > num ? max : num;
                    num = 0;
                    currentLevel++;
                    currentLevelEnd = null;
                }
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                    levelEnd = tmp.left;
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                    levelEnd = tmp.right;
                }
            }
            Console.log("树的最大宽度为: {}, 总层数是: {}", max, currentLevel);
        }
    }

    // 递归中序遍历判断
    public static boolean 判断一个树是二叉搜索树1(TreeNode<Integer> treeRoot) {
        if (treeRoot == null) {
            return true;
        }
        boolean flag = 判断一个树是二叉搜索树1(treeRoot.left);
        if (flag == false || treeRoot.value <= tt) {
            return false;
        } else {
            tt = treeRoot.value;
        }
        return 判断一个树是二叉搜索树1(treeRoot.right);
    }

    // 中序遍历判断
    public static boolean 判断一个树是二叉搜索树2(TreeNode<Integer> treeRoot) {
        if (treeRoot != null) {
            Stack<TreeNode<Integer>> stack = new Stack<>();
            while (treeRoot != null) {
                stack.push(treeRoot);
                treeRoot = treeRoot.left;
            }
            TreeNode<Integer> old = null;
            TreeNode<Integer> tmp = null;
            while (stack.size() > 0 && (tmp = stack.pop()) != null) {
                if (old == null || old.value < tmp.value) {
                    old = tmp;
                } else {
                    return false;
                }
                tmp = tmp.right;
                while (tmp != null) {
                    stack.push(tmp);
                    tmp = tmp.left;
                }
            }
            return true;
        }
        return false;
    }

    // 树形dp 求证一颗树是二叉搜索树
    // 1. 左子树是二叉搜索树  右子树也是二叉搜索树
    // 2. 左孩子的最大值小于当前节点 有孩子的最小值大于当前节点
    public static 二叉搜索树Dp 判断一个树是二叉搜索树3(TreeNode<Integer> treeRoot) {
        if (treeRoot == null) {
            return null;
        }
        二叉搜索树Dp dp = new 二叉搜索树Dp();
        二叉搜索树Dp left = 判断一个树是二叉搜索树3(treeRoot.left);
        二叉搜索树Dp right = 判断一个树是二叉搜索树3(treeRoot.right);

        if ((left == null || (left.bst && left.lMax < treeRoot.value)) && (right == null || (right.bst && right.rMin > treeRoot.value))) {
            dp.bst = true;
        }
        dp.lMax = left != null ? Math.max(treeRoot.value, left.lMax) : treeRoot.value;
        dp.rMin = right != null ? Math.min(treeRoot.value, right.rMin): treeRoot.value;
        return dp;
    }

    public static class 二叉搜索树Dp {
        public boolean bst;
        public int lMax;
        public int rMin;
    }


    // 根据数组 做成一颗树
    public static <T> TreeNode<T> getTreeByHead(T[] data) {
        ArrayList<TreeNode<T>> tmp = new ArrayList<>();
        for (int i = 0; i < data.length; i++) {
            tmp.add(new TreeNode<>(data[i]));
        }
        for (int i = 0; i < data.length; i++) {
            TreeNode<T> node = tmp.get(i);
            int left = 0, right = 0;
            // 寻找左孩子
            if ((left = i * 2 + 1) < data.length) {
                node.left = tmp.get(left);
            } else {
                node.left = null;
            }
            // 寻找右孩子
            if ((right = left + 1) < data.length) {
                node.right = tmp.get(right);
            } else {
                node.right = null;
            }
        }
        return tmp.get(0);
    }

    @Getter
    @Setter
    public static class TreeNode<T> {
        public T value;
        public TreeNode<T> left;
        public TreeNode<T> right;

        public TreeNode() {}

        public TreeNode(T datum) {
            this.value = datum;
        }
    }
}
